package com.wq.sort;

/**
 * @Author: wangqiang20995
 * @Date:2019/3/1
 * @Description:
 * @Resource:
 */
public class InsertSort extends BaseSort {

    public InsertSort(int size) {
        super(size);
    }

    public void insertSortCommon() {
        int[] data = new int[array.length];

        data[0] = array[0];

        int insertPosition;

        for (int i = 1; i < array.length; i++) {
            insertPosition = i;
            int temp = array[i];

            while (insertPosition > 0 && data[insertPosition - 1] > temp) {
                data[insertPosition] = data[insertPosition - 1];
                insertPosition--;
            }

            data[insertPosition] = temp;
        }

        array = data;
    }

    public void binaryInsertionSort() {

        int len = array.length;

        for (int i = 1; i < len; i++) {

            int temp = array[i];  //存储待排序的元素值

            if (array[i - 1] > temp) {  //比有序数组的最后一个元素要小

                int insertIndex = binarySearch(0, i - 1, temp); //获取应插入位置的下标
                for (int j = i; j > insertIndex; j--) {  //将有序数组中，插入点之后的元素后移一位
                    array[j] = array[j - 1];//最后面那个元素已经用temp存起来了
                }

                array[insertIndex] = temp;  //插入待排序元素到正确的位置
            }

        }
    }

    /**
     * 二分查找法
     *
     * @param lowerBound 查找段的最小下标
     * @param upperBound 查找段的最大下标
     * @param target     目标元素
     * @return 目标元素应该插入位置的下标
     */
    public int binarySearch(int lowerBound, int upperBound, int target) {
        int curIndex;
        while (lowerBound < upperBound) {
            curIndex = (lowerBound + upperBound) / 2;
            if (array[curIndex] > target) {
                upperBound = curIndex - 1;
            } else {
                lowerBound = curIndex + 1;
            }
        }
        return lowerBound;
    }

    public static void main(String args[]){
        InsertSort insertSort = new InsertSort(1000000);
//        insertSort.printArray(true);
        long start = System.currentTimeMillis();
//        insertSort.insertSortCommon();
        insertSort.binaryInsertionSort();
        long end = System.currentTimeMillis();
//        insertSort.printArray(true);
        System.out.println("cost:" + (end - start));
    }
}
